import java.util.Arrays;
import java.util.Stack;

public class MySort {
    public static void insertSort(int[] arr){
        for (int i = 1; i <arr.length ; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >=0 ; j--) {
                if(tmp<arr[j]){
                    arr[j+1] = arr[j];
                }
                else {
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }
    public static void shellSort(int[] arr){
        int gap = arr.length;
        while(gap>1){
            gap/=2;
            shell(arr,gap);
        }
    }
    private static void shell(int[]arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-gap;
            for(;j>=0;j-=gap){
                if(arr[j]>tmp){
                    arr[j+gap] = arr[j];
                }
                else break;
            }
            arr[j+gap] = tmp;
        }
    }
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int minindex=i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j]<arr[minindex]){
                    minindex=j;
                }
            }
            swap(arr,i,minindex);
        }
    }
    public static void heapSort(int[] arr){
        createHaep(arr);
        int end = arr.length-1;
        while(end>0){
            swap(arr,0,end);
            shiftDown(arr,0, end);
            end--;
        }
    }
    private static void createHaep(int[] arr){
        int n = (arr.length-2)>>1;
        while(n>=0){
            shiftDown(arr,n,arr.length);
            n--;
        }
    }
    private static void shiftDown(int[]arr,int parent,int length){
        int child = parent*2+1;
        while(child<length){
            if(child+1< length&&arr[child+1]>arr[child]){
                child++;
            }
            if(arr[child]>arr[parent]){
                swap(arr,child,parent);
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }
    public static void bublleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            boolean flg = false;
            for (int j = 0; j < arr.length-1-i; j++) {
                if(arr[j]>arr[j+1]){
                    swap(arr,j,j+1);
                    flg = true;
                }
            }
            if(!flg){
                break;
            }
        }
    }
    public static void quickSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int div = partion(arr,left,right);
        quickSort(arr,left,div-1);
        quickSort(arr,div+1,right);
    }
    private static int partion(int[]arr, int left, int right){
        int i = left;
        int temp = arr[left];
        while(left<right){
            while(left<right&&arr[right]>=temp){
                right--;
            }
            while(left<right&&arr[left]<=temp){
                left++;
            }

            if(left<right)
            swap(arr,left,right);
        }
        swap(arr,i,left);
        return left;
    }

    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public static void quickSortNor(int[]arr){
        int i = 0;
        int j = arr.length-1;
        Stack<Integer> stack = new Stack<>();
        stack.push(i);
        stack.push(j);
        while(!stack.isEmpty()){
            int end= stack.pop();
            int start = stack.pop();
            int div = partion(arr,start,end);
            if(div-1>start){
                stack.push(start);
                stack.push(div-1);
            }
            if(div+1<end){
                stack.push(div+1);
                stack.push(end);
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {4,5,3,2,1};
        quickSortNor(arr);
        System.out.println(Arrays.toString(arr));
    }


}
